module big

fn test_add_in_place() {
	mut a := [u64(1), 2, 3]
	mut b := [u64(5), 6, 7]
	add_in_place(mut a, b)
	assert a == [u64(6), 8, 10]

	a = [u64(11), 10, 11, 12]
	b = [u64(1), 2]
	add_in_place(mut a, b)
	assert a == [u64(12), 12, 11, 12]

	a = []u64{cap: 4}
	a << u64(1)
	a << u64(2)
	b = [u64(3), 4, 5, 6]
	add_in_place(mut a, b)
	assert a == [u64(4), 6, 5, 6]

	a = [u64(0x0423efab_3ce9124b), 0x1438]
	b = [u64(0x0d1dd122_db166062)]
	add_in_place(mut a, b)
	assert a == [u64(0x0141c0ce_17ff72ad), 0x1439]
}

fn test_left_shift_digits_in_place() {
	mut a := [u64(5), 6, 7, 8]
	left_shift_digits_in_place(mut a, 2)
	assert a == [u64(0), 0, 5, 6, 7, 8]
}

fn test_multiply_karatsuba_01() {
	mut a := [u64(3)]
	mut b := []u64{}
	mut c := []u64{len: a.len + b.len, init: 0}
	karatsuba_multiply_digit_array(a, b, mut c)
	assert c == []u64{}

	a = []u64{}
	b = [u64(4)]
	c = []u64{len: a.len + b.len, init: 0}
	karatsuba_multiply_digit_array(a, b, mut c)
	assert c == []u64{}

	a = [u64(3)]
	b = [u64(1)]
	c = []u64{len: a.len + b.len, init: 0}
	karatsuba_multiply_digit_array(a, b, mut c)
	assert c == a

	a = [u64(1)]
	b = [u64(5)]
	c = []u64{len: a.len + b.len, init: 0}
	karatsuba_multiply_digit_array(a, b, mut c)
	assert c == b

	a = [u64(1234)]
	b = [u64(567)]
	c = []u64{len: a.len + b.len + 1, init: 0}
	karatsuba_multiply_digit_array(a, b, mut c)
	assert c == [u64(699_678)]

	a = [u64(0x17ff72ad), 0x1439]
	b = [u64(0x30df2ea6)]
	c = []u64{len: a.len + b.len + 1, init: 0}
	karatsuba_multiply_digit_array(a, b, mut c)
	assert c == [u64(0x0494d164_caf2722e), 0x3dc_51565af6]

	a_operand := integer_from_string('95484736384949495947362') or { panic(err) }
	b_operand := integer_from_string('39474638493') or { panic(err) }
	c = []u64{len: a_operand.digits.len + b_operand.digits.len, init: 0}
	karatsuba_multiply_digit_array(a_operand.digits, b_operand.digits, mut c)
	expected := integer_from_string('3769225450395285038584683507005466') or { panic(err) }
	assert c == expected.digits
}

fn test_multiply_karatsuba_02() {
	a := integer_from_string('53575430359313366047421252453000090528070240585276680372187519418517552556246806124659918940784792906379733645877657341259357264284615702179922887873492874019672838874121154927105373025311855709389770910765') or {
		panic(err)
	}
	b := integer_from_string('977091076523237491790970633699383779582771973038531457285598238843271083830214915826312193418602834034688531898668229388286706296786321423078510899614439367') or {
		panic(err)
	}
	mut c := []u64{len: a.digits.len + b.digits.len + 1, init: 0}
	karatsuba_multiply_digit_array(a.digits, b.digits, mut c)
	expected := integer_from_string('52348074924977237255285644820010078601114587486470740900886892189662650320988400136613780986308710610258879824881256666730655821800564143426560480113864123642197317383052431412305975584645367703594190956925565749714310612399025459615546540332117815550470167143256687163102859337019449165214274088466835988832405507818643018779158891710706073875995722420460085755') or {
		panic(err)
	}
	assert c == expected.digits
}

fn test_multiply_karatsuba_03() {
	a := integer_from_string('9729117383001812976929423642') or { panic(err) }
	b := integer_from_string('36889625830') or { panic(err) }
	mut c := []u64{len: a.digits.len + b.digits.len + 1, init: 0}
	karatsuba_multiply_digit_array(a.digits, b.digits, mut c)
	expected := integer_from_string('358903499915085682930564860470935872860') or { panic(err) }
	assert c == expected.digits
}

fn test_multiply_karatsuba_04() {
	a := integer_from_string('3497162698306482686971441543687784015323935188659503993757455872811087386614092419985044037321104919528005068133951787970585537874489904111916938512842847091721349488467692801057152512166916236213184367524288990504452781825929907470995493661309646347066613682493568745346493010003413738989626609201116716247487999505270467120147815127162127731356094308578608824651183210782207714100237729572853345375454949172401042315228315798079225822021787648873812084227136884600729940854667658626208586874696517348634844052703490897572232568447636899591259434294094321317182661767424480393673432463592896336498353071042650799050700710267095231586270043139333453041015532516541075995479058358831063322267227185753872164375721426686162668623592972867871620133325684441794121727984491920980314378165848724981409299885843916328147796348091243626516406976056911085263146147809470413030865257211209404793514075883680777679138493578810794788543952808891095680872267690') or {
		panic(err)
	}
	b := integer_from_string('3731153765349978524337790303019073866169615820236360525860598113101007652419849831445556596548560058884406106275477847069475858381339095110646794630677741924575724730195310383260858937531720778415641064228137265209604913544897683432011584846544175241128160109960448428720014016539849270207788214347700420341097980912654975389446512856552635037966995033809488867690903720129762695314322725472787603000346202896778207987391285985804181406019619338215824347026372158857600803429407141531830203430317068399662548922504444591385274908074684241297752512843236588392255573848392016559311506271535791162151101220135017417159573887941542933118000377620518732836102365066672711767692414034390790360321914677167248083633551615232080788875425342060374021891940380358579307475843181010943250359217102987258298') or {
		panic(err)
	}
	mut c := []u64{len: a.digits.len + b.digits.len + 1, init: 0}
	karatsuba_multiply_digit_array(a.digits, b.digits, mut c)
	expected := integer_from_string('13048451769827723841923278321193855241872058428961713256963598223823113544308869393875481721028040256602323122921447247203223525228006623227671899134332670311746731440890333942554337434694808695934023689467815943095478675997839202402226439648752044627367822829114336020280929447282163468585404769209994615771773294733509244673189891278506538595789870783779458539371487749876399583947052094519945323844069814095194450349814584625148870057340788686115533159501329566111170880650412359779760456808393370185410432176572682144365401835368082749637208673417028234063907368810782078088911618126690572051133815667647041419960704854062060909165346545952623192359395985743203202132668410599975580175587551065836786982237372286798893118604373993845408861570111075107858370728022568891638898121296878893306306949816814132427209493260832613019444633237775219695833279678133602467177003429529917049633056431504426776487440348449903443579642102845765312131382153105184606682393976592634403346380092701679847372217955349096619505179079762928343558899980175648735397570586605980720828687524561573123038494159647318551197545496201465276098212580839445369200418315000310508759594006187422953054821725336960756926970677282806506256927313164107160898391061464246294174106905930356469329214907846583235734490370187185094462047618230289621171427228984027756484384136106088551265698775255811805670865291484911854071447316265726194982034568878612017100992037975737759552371045887134952857158066446970434610533685859910727214440334704089405629838823453640146362193811088002789803040768301613468217974726406918247619138081429486763003592049227953605769429261539079312619553867710373453222399692311140251766121447367352413232353894344679702619305784387721023140535029791620') or {
		panic(err)
	}
	assert c == expected.digits
}

fn test_multiply_karatsuba_05() {
	a := integer_from_string('82493285896514075384534758557935745817962515879835743030783040173330112080804455282128666887768950832142482683217121022767045108431288465029812097859309605797374125923106819516889369175652710257114598577149674647352808070074171293463437071337278575658048692496764590565606837743827030666885471141044114152998041176796810186287791052484762784126725875326862901808213516742983471605885175506715101338028877662099324668508172829243608350258614718310497987744299914749640568556948763145778198753554058467050519667096099833770026489285130153597761026274548126098456173815617842498193772432207501694106867673557416973930670286653441130602377920992435485420446072373786632480794952955873161165115041514702778052793282025846106368965034233866947381721682937351649336413571927812528541159171383204511499552013936155419845055011752388749268195206809573519780613814964112063870748954135343076802252512193521886335164017829447109689695709486039190070000245645414910990278895308232897116499341219946699993851317981803815406516602176881967155129969593527319125237096519803243326797168917141748725279791872386421043580031403145024863609187112385918738114802920061988765220468749078618853299694217869902560103452546750214562467076096135222593114183955469963751326883227094769527730223248003306708953970243886519739552586227940684171242302412915186263300531140588498540475339456080545078964144209118163323545928290833439765099112126702760509258061959449977429070215529070401124287712461846696193134436630934717425952944747339686188011926730221707166586372593503352250914537732533953216003449759271968770421909127444731638825893567138749890195444') or {
		panic(err)
	}
	b := integer_from_string('6131999155203247409089965800322203420453654507953806420664043731807402839483789086591425043878906721774222779997525063107602234437085033473124680861190605857734959468536446941493399655926830326691521621629120060373092027010394244758024141037091879171132413714138502869706470511932123207420626930454253770927552857807363136786489394763374159969607962219873240941060072539904794844154488056908195189396404340107989455229902431972663610868653304103396580746811591826044603465964167164178855966898012392223090630560777990379102734550082243603230894035356131452642667384300201186297016843973905130369865474318465241408259975202340234896078010895740058413587215886548145454236789540259643610072467034822757986309311709163062352204171299868075798237348977707372770035406598475786685283610490871427030552271811065910679040103566128693521437169494686602257958511710409941630744336034132463653071078769355257935175422990452306401119325390221264671263162134241884024846471010012913485967133615252263790910226344828197924602249009133593805769333128797013042594573917849267639752846975907650362497446525930636106580780824323557414269051915905993675310076325449434427323319596509995607027978958874919018609350403661403557093530969901119390174552941500745876099234877620450622478016638926607899983456508753736077292767888656321808232398065656946197839116825276017609730557227380499217716159012979059487418587202959339426112335872029689748557894665457579061382636201338034208646424996597993168272103220242687875466825791773419606359011555661467526139097341579632208557586297052223542776250948355945042246570') or {
		panic(err)
	}
	mut c := []u64{len: a.digits.len + b.digits.len + 1, init: 0}
	karatsuba_multiply_digit_array(a.digits, b.digits, mut c)
	expected := integer_from_string('505848759427364274329357741986216605130929977294192546489509210457601900426556024040073016771820686868026437733614267409521396918447284490340389690485942051363279925801363126432544321078568099151287021886296438619123380168827268412907813594659842321798217885085110398790053409701983461801115224781834023082890662873169191504305955687046526953897067545715710660155497646914961948331236724535698679813769093322003853124540927645162647300288136882363116067195184081346020194278820548735254637692857032965408070350907222436479366121383668103515786877197427062836511944846826932480466793561731962606417667287322005882211404162719492993874592857953397512491054676297738305916085478022723318784939770402209256271554551983534921497675890891312043569145634049147693960076337369503134427352787659326205647773748112716745925158178083868574895622495928425018774779251441610879114247950357970220146481766134464929967308718872255190412874659776500033163244838173195170196127430202488333101394598915495516818921703991533768617658933173526938837897969225258938562812209445135532692302337200334632389376610492768735714190299971580399753641472989662439382540912225551340987306457743400281084947902809687085442657520101417063633057957437817329020615384515166388289331369947059960847133614170679450523810659652782987668106695354035493369448442611758156006527485718905514811065321814359706644699194418190701868505707278984229585722369789551619919906205950348606361748281997782424695650973254173837814677612994239768420808870410390373336826091130971864943060313050478750611821098669520946650257575417245766405176878592155758047549228495747853203792369590850631203019173404179987735732830481798878566582556613534822512685665712663431843718669560669865410543096239869112140888737377028624106518359554511507606387843187232302200517475850782456324239188729330760193745759978024087469060136973622979394674161020956014241092961397194927506142983436789500109128138664821498501821236619524363279857097783139006599000739982697284955344277927297022159974340926721938079595242213432080401390674728369851144911551677647524015332696130827540662024113950127956097630202663581097770816523549988139863573933413116244923387554856120868464947660075936449421302491693593834507504433415086543597651267221343834170846329492147815735045024399026251779389321698355035556629087431166188787768730306310422839817575075342877250911353135209339455830445625001426381558448651172971413260611230589795224559058399088555025826331277804189489960583576819035715077379287444129934501443336913174870788226087158999934636025721931831136227889916792188808832812760406918544186979726578808350730384441425398168139422687286960377555987296985431654502712799904224867124393655074866476410224402965420326358438396015233973741214619430521493940712748773125913358615541385902712067643691280755344861590017706417595031324052737978011814936301852189889555514450129648152568220313555245236446470869647730471752637583335395835914360683070164833354933631599763359799906362664251738450678551934386687346359703853569505426433767046696609137654729946153837937103113817350588833581432259043880508333957686597572923322695933631607569689529867145971190208528802200404369790036623426263214138627080') or {
		panic(err)
	}
	assert c == expected.digits
}
